{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multi-Qubit Gates Tutorial Workbook\n",
    "\n",
    "**What is this workbook?**\n",
    "A workbook is a collection of problems, accompanied by solutions to them. \n",
    "The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. \n",
    "\n",
    "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [Multi-Qubit Gates tutorial](./MultiQubitGates.ipynb). \n",
    "Since the tasks are offered as programming problems, the explanations also cover some elements of Q# that might be non-obvious for a first-time user.\n",
    "\n",
    "**What you should know for this workbook**\n",
    "\n",
    "You should be familiar with the following concepts before tackling the Multi-Qubit Gates tutorial (and this workbook):\n",
    "1. Basic linear algebra\n",
    "2. The concept of qubit and multi-qubit systems\n",
    "3. Single-qubit and multi-qubit quantum gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 1</span>: Compound Gate\n",
    "\n",
    "**Inputs:** $3$ qubits in an arbitrary superposition state $|\\psi\\rangle$, stored in an array of length 3.\n",
    "\n",
    "**Goal:** Apply the following matrix to the system. This matrix can be represented as applying $3$ single-qubit gates.\n",
    "\n",
    "$$Q = \\begin{bmatrix}\n",
    "    0 & -i & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    i & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & -i & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & i & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & -1 & 0\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "> We recommend to keep a list of common quantum gates on hand, such as [this reference](../../quickref/qsharp-quick-reference.pdf).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution \n",
    "\n",
    "One way to represent a multi-qubit transformation is to use the [tensor product](../LinearAlgebra/LinearAlgebra.ipynb#Tensor-Product) of gates acting on subsets of qubits. For example, if you have 2 qubits, applying the **Z** gate on the first qubit and the **X** gate on the second qubit will create this matrix:\n",
    "\n",
    "$$Z \\otimes X = \\begin{bmatrix} 1 & 0 \\\\ 0 & -1 \\end{bmatrix} \\otimes \\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix} = \\begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & -1 \\\\ 0 & 0 & -1 & 0 \\end{bmatrix}$$\n",
    "\n",
    "With this in mind, let's see how to reverse engineer the target matrix above to find the 3 gates which, acting on individual qubits, together form the target transformation. \n",
    "\n",
    "Start by noticing that the top right and bottom left quadrants of the target matrix are filled with $0$'s, and the bottom right quadrant equals to the top left one, multiplied by $i$. This hints at applying <a href=\"../SingleQubitGates/SingleQubitGates.ipynb#Phase-Shift-Gates\">the $S$ gate</a> to the first qubit:\n",
    "    \n",
    "$$Q = \\begin{bmatrix} 1 & 0 \\\\ 0 & i \\end{bmatrix} \\otimes \n",
    "\\begin{bmatrix}\n",
    "    0 & -i & 0 & 0 \\\\\n",
    "    i & 0 & 0 & 0  \\\\\n",
    "    0 & 0 & 0 & -i \\\\\n",
    "    0 & 0 & i & 0 \n",
    "\\end{bmatrix} = \\begin{bmatrix}\n",
    "    0 & -i & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    i & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & -i & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & i & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & -1 & 0\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Now the $4 \\times 4$ matrix has all $0$s in the top right and bottom left quadrants, and the bottom right quadrant equals to the top left one. This means the second qubit has the $I$ gate applied to it, and the third qubit - the $Y$ gate:\n",
    "\n",
    "$$Q = \\begin{bmatrix} 1 & 0 \\\\ 0 & i \\end{bmatrix} \\otimes \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \\otimes\n",
    "\\begin{bmatrix} 0 & -i \\\\ i & 0 \\end{bmatrix} = S \\otimes I \\otimes Y$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T1_CompoundGate\n",
    "\n",
    "operation CompoundGate (qs : Qubit[]) : Unit is Adj {\n",
    "    S(qs[0]);\n",
    "    I(qs[1]); // this line can be omitted, since it doesn't change the qubit state\n",
    "    Y(qs[2]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 1 of the Multi-qubit Gates tutorial.](../MultiQubitGates/MultiQubitGates.ipynb#Exercise-1:-Compound-Gate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 2</span>: Preparing a Bell state\n",
    "\n",
    "**Input:** Two qubits in state $|00\\rangle$, stored in an array of length 2.\n",
    "\n",
    "**Goal:** Transform the system into the Bell state $\\Phi^+ = \\frac{1}{\\sqrt{2}}\\big(|00\\rangle + |11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution \n",
    "\n",
    "We've seen this state before in the [Multi-Qubit Systems tutorial](../MultiQubitSystems/MultiQubitSystems.ipynb#Exercise-2:-Is-this-state-separable?), where we established that this state is not separable, i.e., it can not be prepared using just the single-qubit gates. To prepare it, we need to use **CNOT** gate.\n",
    "\n",
    "Let's look at the effect of the [CNOT gate](./MultiQubitGates/MultiQubitGates.ipynb#CNOT-Gate) on a separable state described in the tutorial: \n",
    "$$CNOT_{1,2}\\big(\\alpha|0\\rangle + \\beta|1\\rangle\\big) \\otimes |0\\rangle = CNOT_{1,2}(\\alpha|00\\rangle + \\beta|10\\rangle) = \\alpha|00\\rangle + \\beta|11\\rangle$$\n",
    "\n",
    "This resulting state is exactly the state we need to prepare, with $\\alpha = \\beta = \\frac{1}{\\sqrt{2}}$! \n",
    "\n",
    "The solution takes two steps:\n",
    "\n",
    "1. Prepare a state $\\big(\\frac{1}{\\sqrt{2}}|0\\rangle + \\frac{1}{\\sqrt{2}}|1\\rangle\\big) \\otimes |0\\rangle$.  \n",
    "We can use [Hadamard gate](../SingleQubitGates/SingleQubitGates.ipynb#Hadamard) to do this.\n",
    "\n",
    "2. Apply a CNOT take with the first qubit as the control and the second qubit as the target.\n",
    "\n",
    "*You can find a more detailed explanation of the same solution in the [Superposition workbook](../../Superposition/Workbook_Superposition.ipynb#-Task-6.-Bell-state-$|\\Phi^{+}\\rangle$.)*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T2_BellState\n",
    "\n",
    "operation BellState (qs : Qubit[]) : Unit is Adj {\n",
    "    H(qs[0]);\n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 2 of the Multi-qubit Gates tutorial.](../MultiQubitGates/MultiQubitGates.ipynb#Exercise-2:-Preparing-a-Bell-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 3</span>: Swapping two qubits\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. $N$ qubits in an arbitrary state $|\\psi\\rangle$, stored in an array of length $N$.\n",
    "2. Integers `index1` and `index2` such that $0 \\le \\text{index1} < \\text{index2} \\le N - 1$.\n",
    "\n",
    "**Goal:** Swap the states of the qubits at the indices given."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution \n",
    "\n",
    "The SWAP gate allows us to swap the state of any two qubits. In this exercise you need to apply it to two qubits given by their indices in an array of qubits; you can access individual qubits of the array as `qs[index of a qubit]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T3_QubitSwap\n",
    "\n",
    "operation QubitSwap (qs : Qubit[], index1 : Int, index2 : Int) : Unit is Adj {\n",
    "   SWAP(qs[index1], qs[index2]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 3 of the Multi-qubit Gates tutorial.](../MultiQubitGates/MultiQubitGates.ipynb#Exercise-3:-Swapping-two-qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 4</span>: Controlled Rotation\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. Two qubits in an arbitrary state $|\\phi\\rangle$, stored as an array of length 2.\n",
    "2. An angle $\\theta$: $-\\pi < \\theta \\leq \\pi$.\n",
    "\n",
    "**Goal:** Apply a controlled [$R_x$ gate](../SingleQubitGates/SingleQubitGates.ipynb#Rotation-Gates), using the first qubit as control and the second qubit as target, with $\\theta$ as the angle argument for the gate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution \n",
    "\n",
    "In Q# the [Rx](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.rx) gate takes the angle $\\theta$ and the target qubit as inputs. To create a controlled version of this gate, we can use the `Controlled` functor.\n",
    "\n",
    "A matrix representation of this operation would be:\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 &  \\cos\\frac{\\theta}{2} & -i\\sin\\frac{\\theta}{2} \\\\ 0 & 0 & -i\\sin\\frac{\\theta}{2} &  \\cos\\frac{\\theta}{2} \\end{bmatrix} \n",
    "$$\n",
    "\n",
    "The parameters of the new gate are changed a bit: \n",
    "\n",
    "* the first parameter has to be the array of control qubits; the **Rx** gate will be applied to the target only if these are all in the $|1\\rangle$ state. Note that this parameter has to be an array, even if there is just one control qubit!\n",
    "* The second parameter is a tuple with the parameters that you would've passed to the original **Rx** gate. You can create a tuple of values by putting round brackets around them.\n",
    "\n",
    "> The `Controlled` functor can be used before any single qubit gate to make it a controlled gate. The first argument will be an `array` of qubits even if you are using a single control qubit, like in the **CNOT** gate. The second argument is a tuple `()` with the parameters of the gate. For example, these two gates are equivalent: `CNOT(qs[0],qs[1])` and `Controlled X([qs[0]],(qs[1]));`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T4_ControlledRotation\n",
    "\n",
    "operation ControlledRotation (qs : Qubit[], theta : Double) : Unit is Adj {\n",
    "    let controll = qs[0];\n",
    "    let target = qs[1];\n",
    "    Controlled Rx([controll], (theta, target));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 4 of the Multi-qubit Gates tutorial.](../MultiQubitGates/MultiQubitGates.ipynb#Exercise-4:-Controlled-Rotation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 5</span>: Arbitrary controls\n",
    "\n",
    "**Input:**\n",
    "\n",
    "1. `controls` - a register of $N$ qubits in an arbitrary state $|\\phi\\rangle$.\n",
    "2. `target` - a qubit in an arbitrary state $|\\psi\\rangle$.\n",
    "3. `controlBits` - an array of $N$ booleans, specifying what state each control qubit should be in order to apply the gate.\n",
    "\n",
    "**Goal:** Apply the controlled $X$ gate with the `controls` as control qubits and `target` as target, with the state specified by `controlBits` as controls. If the element of the array is `true`, the corresponding qubit is a regular control (should be in state $|1\\rangle$), and if it is `false`, the corresponding qubit is an anti-control (should be in state $|0\\rangle$).\n",
    "\n",
    "> For example, if `controlBits = [true, false, true]`, the controlled $X$ gate should only be applied if the control qubits are in state $|101\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution \n",
    "\n",
    "We are asked to perform a **X** gate on the `target` qubit controlled by the state of `controls` qubits; this state should correspond to the mask given by `controlBits`. \n",
    "\n",
    "If the `controlBits` mask consists of all `true` values, we can use a familiar **Controlled X** gate. What can we do if the mask has some `false` values in it?\n",
    "\n",
    "Turns out we can transform the state of the control qubits depending on the corresponding elements of `controlBits`: if the element is `false`, we apply an **X** gate to the corresponding qubit in the `controls` array. After this, **Controlled X** gate will apply an **X** gate in the exact case that we want.\n",
    "Finally, we'll need to remember to undo (\"uncompute\") the first step, otherwise our controlled gate will affect the state of the control qubits as well as the state of the target. \n",
    "\n",
    "As you can see in the first cell below, this can take quite some coding."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T5_MultiControls\n",
    "\n",
    "operation MultiControls (controls : Qubit[], target : Qubit, controlBits : Bool[]) : Unit is Adj {\n",
    "    for (index in 0 .. Length(controls) - 1) {\n",
    "        if controlBits[index] == false {\n",
    "            X(controls[index]);       \n",
    "        }\n",
    "    }\n",
    " \n",
    "    Controlled X(controls,target);\n",
    "\n",
    "    for (index in 0 .. Length(controls) - 1) {\n",
    "        if controlBits[index] == false {\n",
    "            X(controls[index]);       \n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can shorten the code a bit using the `within ... apply` construct which takes care of uncomputing the steps done in the first code block automatically:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T5_MultiControls\n",
    "\n",
    "operation MultiControls (controls : Qubit[], target : Qubit, controlBits : Bool[]) : Unit is Adj {\n",
    "    within {\n",
    "        for (index in 0 .. Length(controls) - 1) {\n",
    "            if controlBits[index] == false {\n",
    "                X(controls[index]);       \n",
    "            }\n",
    "        }\n",
    "    } apply {\n",
    "        Controlled X(controls,target);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, here is how the exact same task could be realized using the library function [ControlledOnBitString](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T5_MultiControls\n",
    "\n",
    "operation MultiControls (controls : Qubit[], target : Qubit, controlBits : Bool[]) : Unit is Adj {\n",
    "    (ControlledOnBitString(controlBits, X))(controls, target);\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 5 of the Multi-qubit Gates tutorial.](../MultiQubitGates/MultiQubitGates.ipynb#Exercise-5:-Arbitrary-controls)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "Congratulations! You have completed the series of introductory tutorials and are ready to start solving the katas.\n",
    "You should start with the [Basic Gates](../../BasicGates/BasicGates.ipynb) and [Superposition](../../Superposition/Superposition.ipynb) katas."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
